package com.fw.leetcode.dynamicprogram;

import com.fw.leetcode.LeetCode;

/**
 * 70. Climbing Stairs
 *
 * You are climbing a staircase. It takes n steps to reach the top.
 * Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
 *
 * Example 1:
 *  Input: n = 2
 *  Output: 2
 *  Explanation: There are two ways to climb to the top.
 *               1. 1 step + 1 step
 *               2. 2 steps
 * Example 2:
 *  Input: n = 3
 *  Output: 3
 *  Explanation: There are three ways to climb to the top.
 *               1. 1 step + 1 step + 1 step
 *               2. 1 step + 2 steps
 *               3. 2 steps + 1 step
 *
 * Constraints:
 *  1 <= n <= 45
 */
public class Num_0070 implements LeetCode {
    private interface Solution {
        int climbStairs(int n);

        default void assertExpected(int n, int expected) {
            if (climbStairs(n) != expected) {
                climbStairs(n);
            }
        }
    }

    private static class DpRollArraySolution implements Solution {

        @Override
        public int climbStairs(int n) { // 最优：动态规划（滚动数组）：时O(n) 空O(1)
            /*
             * 走 n 步台阶共有几种路径（1步或2步）
             * 最后到终点只有两种途径，走 1 步或 2 步，如下：
             * f(n) = f(n-1) + f(n-2)
             * n 从 0 开始往终点迭代
             * 利用滚动数组优化空间复杂度，去除数组
             */
            int path0;
            int path1 = 1;
            int path2 = 1;
            for (int i = 2; i <= n; i++) {
                path0 = path1;
                path1 = path2;
                path2 = path1 + path0;
            }
            return path2;
        }
    }

    private static class DpArraySolution implements Solution {

        @Override
        public int climbStairs(int n) { // 其次：动态规划：时O(n) 空O(n)
            /*
             * 走 n 步台阶共有几种路径（1步或2步）
             * 最后到终点只有两种途径，走 1 步或 2 步，如下：
             * f(n) = f(n-1) + f(n-2)
             * n 从 0 开始往终点迭代
             */
            int[] path = new int[n+1];
            path[0] = 1;
            path[1] = 1;
            for (int i = 2; i <= n; i++) {
                path[i] = path[i-1] + path[i-2];
            }
            return path[n];
        }
    }

    public static void main(String[] args) {
        Solution solution = new DpRollArraySolution();
        solution.assertExpected(1,1);
        solution.assertExpected(2,2);
        solution.assertExpected(3,3);
    }
}
